The present invention relates in general to program control methods and in particular to a method for allocating memory to a stack cache and for capturing and invoking continuations.
Many computer application programs include a main routine and a set of subroutines. The main routine calls subroutines in some predetermined order, and each subroutine carries out some particular set of operations when called, including, for example, calling another subroutine. When a subroutine completes its operation, it "returns" to its caller by redirecting program operation back to a next instruction of the calling routine.
A computer processor typically includes a set of internal registers for storing data, but since the processor usually does not have enough registers to store all intermediate data results of a routine, programs reserve an area of random access memory called a "stack" for storing such data. FIG. 1 illustrates a typical stack. A portion of the stack ("frame 0") is allocated for use by the main routine of the program. Frame 0 includes a set of memory locations for storing temporary data generated by the main routine. Before the main routine calls a first subroutine (subroutine 1), the main routine stores the memory address (the "return address") of the next main routine instruction executed when subroutine 1 returns to its caller. The main routine also stores a record of the current contents of the various other internal registers of the microprocessor in another portion (the "register record") of frame 0 before making the subroutine call.
When the main routine called subroutine 1, another area of the stack, frame 1, is reserved for subroutine 1. Subroutine 1 thereafter called subroutine 2. But before calling subroutine 2, subroutine 1 also stored its return address and a record of the contents of processor registers in frame 1. As illustrated in FIG. 1, subroutine 2 subsequently called a subroutine 3. A program counter 10 (an internal register of the processor) points to the instruction of subroutine 3 now in execution.
Note that for each routine 0-3, a corresponding frame 0-3 in the stack was reserved. The stack frames may not all be the same size since various routines have different storage requirements for temporary data. A stack pointer register 12 points to the top address of the single active frame.
When subroutine 3 ends, stack space was de-allocated by changing the contents of stack pointer register 12 to point to an address at the top of frame 2. Thus, during further execution of subroutine 2, should subroutine 2 call another subroutine, stack memory space previously allocated to frame 3 is used by the newly called subroutine.
The current state of the stack of FIG. 1 tells us that the processor is now executing subroutine 3, that subroutines 0-2 are now suspended, and that after the processor completes executing subroutine 3, the processor will successively finish executing routines 2, 1, and 0 starting at the return addresses contained in frames 2, 1 and 0. Thus, the stack in some sense is a record showing a future course of program execution.
Some programming languages allow routines to capture and invoke continuations. A "continuation" is a record of the stack as of some moment. For example, when a routine "captures" a continuation, a prior art system may copy the entire contents of the stack and store the copy as a "continuation" in another portion of memory (the "heap"). When a routine invokes (or "throws") a continuation, the current contents of the stack are replaced with a previously captured continuation and program execution resumes with the instruction at the return address included in the top frame of the new stack.
The ability to capture and invoke a continuation permits a program in execution to "save" a record of its future course of action and to re-embark on that future course of action at a later time. Some systems use this control mechanism to save the current state of a program in execution and to subsequently return to that state in response to an interrupt event. Continuation capturing and invoking is also used in multitasking systems to switch between multiple concurrent tasks. Object-oriented programming systems such as Smalltalk employ a continuation (also called a "context") to save the state of an interpreter executing one method before suspending execution of the method and executing some other method. Although the ability to capture and invoke continuations is helpful, the acts of capturing and invoking continuations may be time and memory consuming if the continuations are long.
When continuations have "unlimited extent", they may remain in the memory indefinitely, and a program that captures contexts often may quickly run out of memory space. Therefore, most systems employ some "garbage collection" method for reclaiming memory space occupied by continuations when no longer needed. (A continuation is no longer needed when there is no possibility that the system will execute a suspended routine referencing the continuation.) However, a garbage collector can consume much processing time, causing unacceptable delays ("latency periods") in program execution.